package 剑指专题.链表;


/*
 * Author：江松
 * Date：2023/3/26 10:18
 *
 从尾到头打印链表
 */

import org.omg.CORBA.INTERNAL;

import java.util.ArrayList;
import java.util.Stack;

public class Main1 {
        public class ListNode {
       int val;
       ListNode next = null;

              ListNode(int val) {
           this.val = val;
       }
   }

   //递归
    ArrayList<Integer>res=new ArrayList<>();
    public void dfs(ListNode p){
            if(p==null)return;
            dfs(p.next);
            res.add(p.val);
    }

   public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        dfs(listNode);
        return res;
   }


   /*
   //O(n^2)数组插入
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer>ans=new ArrayList<>();
        ListNode p=listNode;
        while (p!=null){
            ans.add(0,p.val);
            p=p.next;
        }
        return ans;
    }
    */
}
